package 典型.动态规划;

public class BagMulti {
    public static int manyPack(int V,int N,int[] weight,int[] value,int[] num){
        int[][] dp = new int[N+1][V+1];
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                if(weight[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else{
                    //考虑物品的件数限制
                    int maxV = Math.min(num[i-1],j/weight[i-1]);
                    for(int k=1;k<maxV+1;k++){
                        dp[i][j] = Math.max(dp[i][j], Math.max(dp[i - 1][j], dp[i - 1][j - k * weight[i - 1]] + k * value[i - 1]));
                    }
                }
            }
        }
        return dp[N][V];
    }
}
